# 给你一个长度为 n 的整数数组
#  nums ，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。 
# 
#  我们是这样定义一个非递减数列的： 对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。 
# 
#  
# 
#  示例 1: 
# 
#  
# 输入: nums = [4,2,3]
# 输出: true
# 解释: 你可以通过把第一个 4 变成 1 来使得它成为一个非递减数列。
#  
# 
#  示例 2: 
# 
#  
# 输入: nums = [4,2,1]
# 输出: false
# 解释: 你不能在只改变一个元素的情况下将其变为非递减数列。
#  
# 
#  
# 
#  提示： 
#  
# 
#  
#  n == nums.length 
#  1 <= n <= 10⁴ 
#  -10⁵ <= nums[i] <= 10⁵ 
#  
# 
#  Related Topics 数组 👍 798 👎 0
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        count = 0
        for i in range(len(nums)-1):
            if nums[i] > nums[i + 1]:
                count += 1
                if count > 1:
                    return False
                if i==0:
                    nums[i] = nums[i+1]
                elif i==len(nums)-2:
                    if nums[i+1] >= nums[i-1]:
                        nums[i] = nums[i+1]
                    else:
                        nums[i+1] = nums[i]
                # 因为i的范围是[1,n-2],故要先处理几个剩下的
                #  这个时候是调小i 还是调大i+1?
                else:
                    if nums[i + 1] >= nums[i-1]:
                        # 降i
                        nums[i] = nums[i+1]

                    # 升i+1
                    elif nums[i + 2] > nums[i]:
                        nums[i+1] = nums[i]
                    else:
                        return False
        return True


# leetcode submit region end(Prohibit modification and deletion)

# 5 7 1 8 和 4 2 3
print(Solution().checkPossibility(nums=[1,4,1,2]))
